#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

int maxPathSum(TreeNode *root);
void maxPathSumSub(TreeNode *root, int &maxRootLeaf, int &maxInner);

int main(int argc, char **argv){

    TreeNode root(2);
    TreeNode left(-1);
    root.left = &left;
    /*
    TreeNode lleft(10);
    TreeNode lright(20);
    left.left = &lleft;
    left.right = &lright;
    TreeNode right(3);
    root.left = &left;
    root.right = &right;
    */
    cout<<maxPathSum(&root)<<endl;

    return 0;
}

int maxPathSum(TreeNode *root) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if(!root)
        return 0;

    int maxRootLeaf, maxInner;
    maxPathSumSub(root, maxRootLeaf, maxInner);

    return maxInner;
}

void maxPathSumSub(TreeNode *root, int &maxRootLeaf, int &maxInner){
    if(!root){
        maxRootLeaf = 0x80000000;
        maxInner = 0x80000000;
        return;
    }

    int maxRootLeafLeft, maxRootLeafRight;
    int maxInnerLeft, maxInnerRight;
    maxPathSumSub(root->left, maxRootLeafLeft, maxInnerLeft);
    maxPathSumSub(root->right, maxRootLeafRight, maxInnerRight);
    // maxRootLeaf
    maxRootLeaf = root->val;
    int rootGreater = (maxRootLeafLeft > maxRootLeafRight ? maxRootLeafLeft : maxRootLeafRight);
    if(rootGreater > 0){
        maxRootLeaf += rootGreater;
    }
    // maxInner
    // could be root, left+root, right+root, left+right+root, leftinner, rightinner
    maxInner = root->val;
    if(maxRootLeafLeft > 0)
        maxInner += maxRootLeafLeft;
    if(maxRootLeafRight > 0)
        maxInner += maxRootLeafRight;
    int innerInnerMax = maxInnerLeft > maxInnerRight ? maxInnerLeft : maxInnerRight;
    if(innerInnerMax > maxInner){
        maxInner = innerInnerMax;
    }
    return;
}